A Microfiche Appendix comprising one sheet, totaling twenty-seven frames is included herewith.
A portion of the disclosure of this patent document contains material that is subject to copyright protection. The copyright owner has no objection to the reproduction of the patent document or the patent disclosure in exactly the form it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
The present invention relates to memory circuits for microprocessors.
The operation of processors frequently involves temporary storage of information for later manipulation. As is well known, data may be stored for random access, or may be stored for access in an ordered fashion such as in a stack or queue. A queue stores data entries in sequential fashion, so that the oldest entry in the queue is retrieved first. The entry and removal of data in queues may be handled by a central processing unit (CPU) processing software instructions.
Such a queue system can be a bottleneck in the efficient operation of the processor. For example, a first item of information obtained from one process may need to be queued to wait for the processing of another item of information, so that both items may then be manipulated together by the processor. The queuing and dequeuing of the first item of information may require additional work of the processor, slowing the eventual processing of both items of information further. More complicated situations involving multiple operands and operations cause the queuing and dequeuing complications to multiply, requiring various locks that absorb further processing power and time. The size and complexity of a microprocessor can lead to correspondingly large and complex arrangements for storing queues.
The allocation of memory space for these queues is also challenging, as the queues can vary in length depending upon the type of operations being processed. For example, a queuing scheme for a communication system is described by Delp et al. in U.S. Pat. No. 5,629,933, in which a number of data packets are stored in first-in, first out (FIFO) order in queues that are segregated by session identity. Depending upon activity of a particular session, the number of entries in such queues could be very large or zero. In U.S. Pat. No. 5,097,442, Ward et al. teach programming a variable number into a register to store that number of data words in a FIFO memory array, up to the limited size of that array.
To distribute memory for queuing different connections, U.S. Pat. No. 5,812,775 to Van Seters et al. teaches a device for a router having a number of network connections that dedicates specific buffers to each network connection as well as providing a pool of buffers for servicing any network connection. A number of static random access memory (SRAM) queues are maintained for tracking buffer usage and allocating buffers for storage. While SRAM provides relatively quick access compared to dynamic random access memory (DRAM), SRAM memory cells are much larger than DRAM, making SRAM relatively expensive in terms of chip real estate.
The present invention provides a mechanism for queuing information that is fast, flexible and efficient. The mechanism combines the speed of SRAM with the low cost and low power consumption of DRAM, to enable significant expansion of high-speed data storage in queues without corresponding increases in costs. The queues may be manipulated by hardware or software, and may provide processing events for an event-driven processor. While the queuing mechanism of the present invention can be employed in many systems in place of conventional queues, particular utility is found where high speed access to queues is beneficial, as well for situations in which flexible queue size may be an advantage, and/or for cases where the smaller size and lower cost of DRAM compared to SRAM is of value.